\setcounter{listing}{0}
\chapter{循环链表与双向链表}
\section{实验目的}
\begin{itemize}
  \item 通过本次实验进一步加深对循环链表、双向链表的理解,在此基础上实现循环链表、双向链表的链式表示；
  \item 掌握循环链表、双向链表的基本操作(包括:创建、插入、删除、 查找等基本操作)；
  \item 在掌握基本操作的基础上,对实验给出的扩展实验题目进行分析、 建模。使用循环链表、双向链表及简单的算法解决问题。
\end{itemize}

\section{基础实验题目}
在本次实验当中，你需要实现\textbf{循环链表}\emph{或}\textbf{双向链表}，其中循环链表表及双向链表的结构定义及操作接口定义分别见\ref{sec:cllist}和\ref{sec:dllist}。

需要注意的是，在本次实验当中，你需要完成\ref{sec:cllist}\emph{或}\ref{sec:dllist}的内容（二选一），在完成上述内容后，请使用你实现的\textbf{循环链表}\emph{或}\textbf{双向链表}完成\ref{sec:listtest2}所给出的题目，用于测试你的程序是否正确。

\subsection{循环链表数据结构的定义及操作接口声明}
\label{sec:cllist}
循环链表是在单链表的基础上做了改进，使得链表中最后一个结点的\textbf{link域}不再指向\textbf{NULL}，而是指向\textbf{头结点}。以下给出循环的数据结构定义以及操作接口声明(C语言描述):

\captionof{listing}{循环链表数据结构定义及操作接口声明}
\label{lstcllistadt}
\begin{minted}[linenos, frame=single]{c}
struct CLNode;
typedef int ELEMTYPE;
typedef int SIZE_T;
typedef struct CLNode *POSITION;
typedef struct CLNode *PNode;

struct CLNode {
  ELEMTYPE info;
  PNode linke;
};

struct clList {
  PNode head;
  PNode rear;
  SIZE_T length;
};

typedef struct clList *CLList;

CLList createCLList(void);
void destroyCLList(CLList *list);

void printCLList(CLList list);
int lengthCLList(CLList list);

int insertPostCLList(CLList list, POSITION p, ELEMTYPE x);
int insertPreCLList(CLList list, POSITION p, ELEMTYPE x);
int appendElemCLList(CLList list, ELEMTYPE x);

int deleteElemCLList(CLList list, ELEMTYPE x);
int deleteVertexCLList(CLList list, POSITION p);

POSITION locateVertexCLList(CLList list, ELEMTYPE x);
\end{minted}

在代码\ref{lstcllistadt}中，我们为\emph{clList}结构体定义了3个成员：
\begin{itemize}
  \item \emph{head}用于指向循环链表中头结点；
  \item \emph{rear}用于指向循环链表中的尾结点\footnote{尾结点指针的定义并非必须。在此我们为了方便实现循环链表的外部插入操作，引入了尾指针的概念。读者可以自行决定是否采用尾指针。}；
  \item \emph{length}用于表示当前循环链表中数据元素的个数\footnote{与顺序表不同的是，链式表的结点存储空间均是通过动态内存分配获得，因此不存在元素个数的限制}；
\end{itemize}

\subsection{双向链表的数据结构定义及操作接口声明}
\label{sec:dllist}

在此给出双向链表的数据结构定义(C语言描述):

\captionof{listing}{双向链表数据结构定义及操作接口声明}
\begin{minted}[linenos, frame=single]{c}
typedef int ELEMTYPE;

struct DLNode;
typedef int SIZE_T;
typedef struct DLNode *PNode;
typedef struct DLNode *POSITION;

struct DLNode {
  ELEMTYPE info;
  PNode llink;
  PNode rlink;
};

struct dlList{
  PNode head;
  Pnode rear;
  SIZE_T length;
};

typedef struct dlList *DLList;

DLList createDLList(void);
void destroyDLList(DLList *list);

void printDLList(DLList list);
int lengthDLList(DLList list);

int insertPostDLList(DLList list, POSITION p, ELEMTYPE x);
int insertPreDLList(DLList list, POSITION p, ELEMTYPE x);
int appendElemDLList(DLList list, ELEMTYPE x);

int deleteElemDLList(DLList list, ELEMTYPE x);
int deleteVertexDLList(DLList list, POSITION p);

POSITION locateVertexDLList(DLList list, ELEMTYPE x);
\end{minted}

\subsection{测试题目}
\label{sec:listtest2}

请使用你在\ref{sec:cllist}和\ref{sec:dllist}中所实现的循环链表\emph{或}双向表来完成本节内容。
并编写相应的测试程序对你所创建的循环链表\emph{或}双向链表进行测试,以下给出测试样例要求:

\subsubsection*{问题描述}

在本题中，你需要编写程序用于解析题目所给出的各类线性表操作的命令，并测试你所实现的线性表所定义的
操作接口是否能正确的工作。

\subsubsection*{输入数据格式}

输入包含1个测试用例，第一行只有一个整型数$N(0 < N < 100)$,表明接下来有$N$行命令, 命令可以为如下格式：

\begin{small}
\begin{description}
  \item[CREATE m] 创建一个长度为$m$表，其中$m$为整型数，且$0 < m < 100$。
  \item[DESTROY]  销毁表；表销毁后不可再使用。
  \item[PRINT]    在一行中打印出表中所有元素，每个元素之间用一个空格作为间隔，注意最后一个元素后无空格。
  \item[LENGTH]   输出表的长度。
  \item[ELEMENT p] 获取下标为$p$的节点，并将其元素值作为单独一行输出。题目确保$p$是合法有效的范围($0 <= p <= \textbf{size()}-1$)。
  \item[FIND x]   查找表中是否存在元素值为$x$的结点，如果存在的话则输出该节点的下标，如果不存在则输出$-1$。  
  \item[BEFORE p x] 在下标为$p$的结点\textbf{前}插入一个新的结点，其值为$x$；我们确保$p$是合法有效的范围($0 <= p <= \textbf{size()}-1$)。
  \item[AFTER p x] 在下标为$p$的结点\textbf{后}插入一个新的结点，其值为$x$；我们确保$p$是合法有效的范围($0 <= p <= \textbf{size()}-1$)。
  \item[DELETE x] 删除表中元素值为$x$的第一个结点。
  \item[REMOVE p] 删除表中下标为$p$的结点；我们确保$p$是合法有效的范围($0 <= p <= \textbf{size()}-1$)。
  \item[APPEND x] 在表的尾部添加一个新结点，其元素值为$x$。
\end{description}
\end{small}

\subsubsection*{输出格式}

对于输入中的每一个命令，按照其命令的含义及要求输出(注意：请不要多输出也不要少输出)。

\subsubsection*{输入样例}

\begin{lstlisting}[frame=none, numbers=none]
  11
  CREATE 5
  APPEND 1
  AFTER 0 2
  AFTER 0 3
  AFTER 0 4
  AFTER 0 5
  PRINT
  REMOVE 3
  REMOVE 3
  PRINT
  DESTROY
\end{lstlisting}

\subsubsection*{输出样例}
\begin{lstlisting}[frame=none, numbers=none]
  1 5 4 3 2
  1 5 4
\end{lstlisting}

\subsubsection*{Hint}
在循环链表及双向链表的操作接口定义中，结点位置的采用\textbf{POSITION}类型表示转换为\textbf{int}
型表示，可参照代码\ref{Index2Pos}

\section{扩展实验题目}

\subsection{一元多项式加减运算求值}
\subsubsection*{问题描述}

你需要实现一元多项式相加减问题，例如有如下两个一元多项式:

$A = 4 - 2 \cdot X + 3 \cdot X^{2} - 5 \cdot X^{19}$

$B = 2 \cdot X - 4 \cdot X^{3} + 7 \cdot X^{7}$

则有

$A + B = 4 + 3 \cdot X^{2} - 4 \cdot X^{3} + 7 \cdot X^7 - 5 \cdot X^{19}$

$A - B = 4 - 4 \cdot X + 3 \cdot X^{2} + 4 \cdot X^{3} - 7 \cdot X^{7} - 5 \cdot X^{19}$

你的任务是给定多项式\emph{A}和\emph{B}以及计算的命令(加或减)，计算出\emph{A}和\emph{B}的运算结果。

\subsubsection*{输入格式}
输入包含多个测试用例，每个测试用例第一行包含3个整型数$n$，$m$($0 < n, m < 100$)以及$X$，表示一元多项式\emph{A}和\emph{B}分别包含$n$和$m$项，接下来的一行包含表示进行\textbf{加法}或\textbf{减法}运算的命令(\textbf{ADD}或\textbf{SUBSTRACT})；

接下来的$n$行表示\emph{A}式的所有项，每行包含2个整型数\emph{s}和\emph{e}，分别表示该项的系数和指数；
接下来的$m$行表示\emph{B}式的所有项，每行包含2个整型数\emph{s}和\emph{e}，分别表示该项的系数和指数；
最后一个测试用例以0 0 0作为开头，该测试用例不需要处理。

我们确保多项式计算后的结果可用\emph{int}表示。
\subsubsection*{输出格式}
对于每个测试用例输出\emph{A}和\emph{B}根据计算命令所得结果，每个结果单独占一行。

\subsubsection*{输入样例}
\begin{lstlisting}[frame=none, numbers=none]
4 3 1
ADD
4 0
3 2
-2 1
-5 19
2 1
-4 3
7 7
4 3 2
SUBSTRACT
4 0
-2 1
-5 19
3 2
2 1
-4 3
7 7
0 0 0
\end{lstlisting}

\subsubsection*{输出样例}
\begin{lstlisting}[frame=none, numbers=none]
5
-5
\end{lstlisting}

\subsection{Josephus问题}

\subsubsection*{问题描述}
设有$N$个人围坐在一个圆桌周围,现从第$s$个人开始报数，数到第$m$个人出列，然后从出列的下一个人重新开始报数，
数到第$m$个人又出列，......如此反复直到所有的人全部出列为止。
你需要编写程序来完成该问题：对于任意给定的$N$($0 < N < 1000$)、$s$($0 < s < N$)和$m$($0 < m < N$)，求按上述出列规则最后一个出列的人的编号。

\subsubsection*{输入格式}
输入包含多个测试用例，每一个测试用例包含三个$N$，$s$，$m$整型数，三个数之间用一个空格作为间隔，
分别表示人数$N$，以及开始报数的第$s$个人以及第$m$个人出列。

最后一个测试用例以0 0 0作为结束，该测试用例不需要处理。

\subsubsection*{输出格式}
对于每一个测试用例，输入一行，仅包含一个整型数，表示最后一个出列的人的编号。

\subsubsection*{输入样例}
\begin{lstlisting}[frame=none, numbers=none]
8 1 4
5 1 3
8 1 9
8 1 1
15 3 9
0 0 0
\end{lstlisting}

\subsubsection*{输出样例}

\begin{lstlisting}[frame=none, numbers=none]
6
4
8
8
2
\end{lstlisting}
